1611-使整数变为 0 的最少操作次数

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

示例 1：

**输入：** n = 3
**输出：** 2
**解释：** 3 的二进制表示为 "11"
" **1** 1" -> " **0** 1" ，执行的是第 2 种操作，因为第 0 位为 1 。
"0 **1** " -> "0 **0** " ，执行的是第 1 种操作。

示例 2：

**输入：** n = 6
**输出：** 4
**解释：** 6 的二进制表示为 "110".
" **1** 10" -> " **0** 10" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"01 **0** " -> "01 **1** " ，执行的是第 1 种操作。
"0 **1** 1" -> "0 **0** 1" ，执行的是第 2 种操作，因为第 0 位为 1 。
"00 **1** " -> "00 **0** " ，执行的是第 1 种操作。

提示：

• 0 <= n <= 109

解题思路

自己看的笔记:见注释

代码

class Solution {
public:
    int minimumOneBitOperations(int n) {
        //先求出某个位置是1后续都是0，该位置往后都变为0需要的操作步骤；以及某个位置往后都是0，该位置变为1的操作次数;这里用dp
        //然后从最低位的1开始往高位走去消掉每个1，每个位置有两种可能的走法：1.该位置的前一个位置翻转，然后该位置往后都变为0;
        //2.该位置直接变为0(这里也是个dp)
        int zeroToOne[31];
        int oneToZero[31];
        zeroToOne[0] = 1;
        oneToZero[0] = 1;
        for(int i = 1;i<=30;i++){
            zeroToOne[i] = zeroToOne[i-1] + 1 + oneToZero[i-1];
            oneToZero[i] = zeroToOne[i-1] + 1 + oneToZero[i-1];
        }
        int C[31];
        for(int i = 0;i<=30;i++){
            C[i] = -1;
        }
        return process(oneToZero,zeroToOne,n,0,C);
    }
private:
    int process(int* oneToZero, int* zeroToOne,int n, int index, int* C){
        if(n==0){
            return 0;
        }
        if((1<<index & n) == 0){
            return process(oneToZero,zeroToOne,n,index+1,C);
        }
        if((n&(n-1)) == 0){//二进制只有index位置一个1
            return oneToZero[index];
        }
        if(C[index] != -1){
            return C[index];
        }
        int res = min(process(oneToZero,zeroToOne,n^(1<<index),index+1,C) + oneToZero[index],process(oneToZero,zeroToOne,n^((1<<index)|(1<<index+1)),index+1,C) + oneToZero[index]+1);
        C[index] = res;
        return res;
    }
};
//10